package _220330;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-30-10:19
 */

/** https://blog.csdn.net/qq_51439643/article/details/121364655
 *  共有N个礼物，需要进行M次打包，希望让每个人得到的包裹连续且最大重量最小，假设所有礼物的总重量为sum ,
 *  所有礼物中最重的礼物为max ,那么答案只有能可能出现[max,sum] 这个区间内部，
 *  我们可以给定一个属于区间[max,sum]的一个重量target为每个包裹可以装入的最大重量。
 * ​那么我们如何判断target最大重量下能够进行M次打包呢？因为打包的礼物必须是连续的，
 *  因此从第一个礼物开始遍历，看看最大重量target下 N 个礼物需要打多少个包,
 *  如果小于等于M，说明每个包最大重量为target是能够装下，符合题意。
 *  题目要求尽量获得最小的重量，这里使用二分的方法，左区间：max，右区间：sum，
 *  封装函数judge判断能够打包 ，取区间中间值mid，
 *  如果judge判断为true，说明mid下能满足题意，right=mid,否则left=mid+1,直到遍历出结果
 */
public class 打包 {
    static int n, m;
    static int[] w;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        w = new int[n + 1];
        int l = 0 ,r = 0;
        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            r += w[i];  // 统计N个礼物的总量
        }
        // 二分查找答案
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(w, mid, m)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(l);
    }

    /**
     * 判断某个礼物能否放进之前的总量为maxWeight的包裹 不行再开一个包裹
     * @param w
     * @param maxWeight：当前包裹可以存放的最大总量
     * @param m：包裹数量（尽可能地少 最多就是m个）
     * @return
     */
    private static boolean check(int[] w, int maxWeight, int m) {
        int curWeight = 0;  // 保存当前这个包的重量
        int curPackage = 1; // 保存的需要打包数量
        for (int val : w) {
            // 如果超出了所给定的最大打包数量，返回false
            if (val > maxWeight) {
                return false;
            }
            curWeight += val;
            // 超过了单个包的最大重量，打一个新的包
            if (curWeight > maxWeight) {
                curWeight = val;
                curPackage += 1;
            }
        }
        return curPackage <= m;
    }
}
